home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2002 November / SGI Freeware 2002 November - Disc 2.iso / dist / fw_glimpse.idb / usr / freeware / src / glimpse-3.0 / index / region.c.z / region.c
C/C++ Source or Header  |  1997-09-09  |  14KB  |  571 lines
  1. /* Copyright (c) 1994 Sun Wu, Udi Manber, Burra Gopal.  All Rights Reserved. */
  2. /* From mail received from Bill Camargo and Darren Hardy in June 1994 */
  3. #include <stdio.h>
  4. #include "region.h"
  5.  
  6. /*
  7.  * Exports the following routines. Any filtering/attr-val parsing mechanism
  8.  * can be integrated into glimpse and glimpseindex with this interface.
  9.  */
  10.  
  11. char * /* attrname = */ attr_id_to_name(/* int attrid */);
  12. int /* attrid = */ attr_name_to_id(/* char *attrname */);
  13. int attr_dump_names(/* char *filename */);
  14. int attr_load_names(/* char *filename */);
  15. int attr_free_table(/* void */);
  16. int region_initialize(/* void */);
  17. int region_destroy(/* void */);
  18. int region_create(/* char *filename */);
  19. int /* attrid = */ region_identify(/* int offset_in_file, int len_of_region */);
  20.  
  21. #if    BG_DEBUG
  22. extern int memory_usage;
  23. #endif    /* BG_DEBUG*/
  24.  
  25. #if    STRUCTURED_QUERIES
  26.  
  27. printsp()
  28. {
  29.     int    x;
  30.  
  31.     printf("stack at %x\n", &x);
  32. }
  33.  
  34. /*****************************************************************************/
  35.  
  36. #define ATTR_HASH_TABLE_SIZE    256    /* must be a power of 16=multiple of 4 bits */
  37. #define ATTR_HASH_TABLE_MASK    0xff    /* bits that mask off the bits in TABLE_SIZE */
  38. #define ATTR_HASH_STEP_SIZE    2    /* #of nibbles that make up TABLE_SIZE */
  39.  
  40. attr_element_t    *attr_hash_table[ATTR_HASH_TABLE_SIZE];
  41. char    **attr_name_table = NULL;
  42. int    attr_num = 0;
  43. int    attr_maxid = 0;
  44.  
  45. /* English language characters have all info in lowest 4 bits */
  46. int
  47. attr_hash_index(word, len)
  48.     char    *word;
  49.     int    len;
  50. {
  51.     int    i=0, j, index = 0, temp;
  52.  
  53.     for (i=0; i+ATTR_HASH_STEP_SIZE<=len; i+=ATTR_HASH_STEP_SIZE) {
  54.         temp = 0;
  55.         for (j=0; j<ATTR_HASH_STEP_SIZE; j++)
  56.             temp = (temp << 4) | word[i+j] & 0x0f;
  57.         index = (index + temp) & ATTR_HASH_TABLE_MASK;
  58.     }
  59.     temp = 0;
  60.     for (j=0; i+j<len; j++)
  61.         temp = (temp << 4) | word[i+j] & 0x0f;
  62.     index = (index + temp) & ATTR_HASH_TABLE_MASK;
  63.     return index;
  64. }
  65.  
  66. char *
  67. attr_id_to_name(id)
  68.     int    id;
  69. {
  70. #if    0
  71.     printf("id = %d\n", id);
  72. #endif    /*0*/
  73.     if ((attr_name_table == NULL) || (id > attr_maxid)) return NULL;
  74.     else return attr_name_table[id];
  75. }
  76.  
  77. /*
  78.  * returns the attribute number associated with name, 0 for no attribute --
  79.  * NOTE: name may not be null terminated and you are not allowed to alter it.
  80.  * called during indexing and search.
  81.  */
  82. int
  83. attr_name_to_id(name, len)
  84.     char    *name;
  85.     int    len;
  86. {
  87.     int        index = attr_hash_index(name, len);
  88.     attr_element_t    *e = attr_hash_table[index];
  89. #if    0
  90.     char        c = name[len];
  91.     name[len] = '\0';
  92.     fprintf(stderr, "attr=%s @ %d?\n", name, index);
  93.     fflush(stderr);
  94.     name[len] = c;
  95. #endif    /*0*/
  96.  
  97.     while(e != NULL) {
  98.         if (!strncmp(e->attribute, name, len)) break;
  99.         else e = e->next;
  100.     }
  101.     if (e!=NULL) {
  102. #if    0
  103.         fprintf(stderr, "foundid=%d\n", e->attributeid);
  104. #endif    /*0*/
  105.         return e->attributeid;
  106.     }
  107.     return 0;
  108. }
  109.  
  110. /*
  111.  * returns the attribute number (> 0) for the attribute "name". It adds the
  112.  * name as a newly seen attribute if it doesn't exist already (using #tables).
  113.  * called in region_create, which is called during indexing.
  114.  */
  115. attr_insert_name(name, len)
  116.     char    *name;
  117.     int    len;
  118. {
  119.     int        index = attr_hash_index(name, len);
  120.     attr_element_t    **pe = &attr_hash_table[index], *e;
  121.  
  122.     while(*pe != NULL) {
  123.         if (!strcmp((*pe)->attribute, name)) break;
  124.         else pe = &(*pe)->next;
  125.     }
  126.     if (*pe!=NULL) return (*pe)->attributeid;
  127.  
  128.     e = (attr_element_t *)my_malloc(sizeof(attr_element_t));
  129.     e->attribute = (char *)my_malloc(len + 2);
  130.     strncpy(e->attribute, name, len + 1);
  131.     e->attributeid = (++attr_num);
  132.     e->next = NULL;
  133.     *pe = e;
  134. #if    0
  135.     fprintf(stderr, "inserting %s %d\n", name, attr_num);
  136. #endif    /*0*/
  137.     return e->attributeid;
  138. }
  139.  
  140. /*
  141.  * frees current hash table of attr-value pairs.
  142.  * called after dump in indexing, and at end of search (after previous load).
  143.  */
  144. int
  145. attr_free_table()
  146. {
  147.     int    i;
  148.     attr_element_t *e, *temp;
  149.  
  150.     for (i=0; i<ATTR_HASH_TABLE_SIZE; i++) {
  151.         e = attr_hash_table[i];
  152.         while (e != NULL) {
  153.             temp = e->next;
  154. #if    BG_DEBUG
  155.             memory_usage -= strlen(e->attribute) + 2;
  156. #endif    /*BG_DEBUG*/
  157.             my_free(e->attribute, 0);
  158.             my_free(e, sizeof(attr_element_t));
  159.             e = temp;
  160.         }
  161.         attr_hash_table[i] = NULL;
  162.     }
  163.     if (attr_name_table != NULL) {
  164.         my_free(attr_name_table, sizeof(attr_element_t *) * ATTR_HASH_TABLE_SIZE);
  165.         attr_name_table = NULL;
  166.     }
  167.     return 0;
  168. }
  169.  
  170. /* Looks for embedded attributes and copies the real attribute into dest */
  171. attr_extract(dest, src)
  172.     char    *dest, *src;
  173. {
  174.     char    *oldsrc = src;
  175.  
  176. check_again:
  177.     if (!strncmp("embed<", src, 6) || !strncmp("Embed<", src, 6) || !strncmp("EMBED<", src, 6)) {
  178.         src += 6;
  179.         while ((*src != '>') && (*src != '\0')) src++;
  180.         if (*src == '\0') {
  181.             strcpy(dest, oldsrc);
  182.             return;
  183.         }
  184.         while (!isalnum(*src)) src ++;    /* assuming type names are .. */
  185.         oldsrc = src;
  186.         goto check_again;
  187.     }
  188.     strcpy(dest, src);
  189.     return;
  190. }
  191.  
  192. /*
  193.  * dumps the attribute-list into a file name (id, name, \n)
  194.  * into the file specified and then destroys the hash table.
  195.  * Returns #of attributes dumped into the file, -1 if error.
  196.  * called at the end of indexing.
  197.  */
  198. int
  199. attr_dump_names(filename)
  200.     char    *filename;
  201. {
  202.     int    i=0;
  203.     int    ret = -1;
  204.     FILE    *fp = fopen(filename, "w");
  205.     attr_element_t *e;
  206.  
  207. #if    0
  208.     printf("in dump attr\n");
  209. #endif    /*0*/
  210.     if (fp == NULL) return -1;
  211.     ret = 0;
  212.     for (i=0; i<ATTR_HASH_TABLE_SIZE; i++) {
  213.         e = attr_hash_table[i];
  214.         while (e != NULL) {
  215.             fprintf(fp, "%d,%s ", e->attributeid, e->attribute);
  216.             e = e->next;
  217.             ret ++;
  218.         }
  219.         fputc('\n', fp);
  220.     }
  221.     fflush(fp);
  222.     fclose(fp);
  223.     return ret;
  224. }
  225.  
  226. /*
  227.  * constructs a hash-table of attributes by reading them from the file.
  228.  * Returns #of attributes read from the file, -1 if error.
  229.  * Does not recompute hash-indices of attributes.
  230.  * called before searching for attr=val pairs.
  231.  */
  232. int
  233. attr_load_names(filename)
  234.     char    *filename;
  235. {
  236.     int    index = 0, ret = 0;
  237.     FILE    *fp = fopen(filename, "r");
  238.     attr_element_t *e;
  239.     int    c = 0;
  240.     char    temp[1024];    /* max attr name */
  241.     char    buffer[1024+32];/* max attr id pair */
  242.     int    i;
  243.     int    id;
  244.  
  245.     attr_maxid = 0;
  246.     memset(attr_hash_table, '\0', sizeof(attr_element_t *) * ATTR_HASH_TABLE_SIZE);
  247.     if (fp == NULL) return -1;
  248.     while ((c = getc(fp)) != EOF) {
  249.         if (c == '\n') {
  250.             index ++;
  251.             continue;
  252.         }
  253.         ungetc(c, fp);
  254.         /* fscanf screws up fp and skips over trailing space characters (\t,\n, ) */
  255.         i=0;
  256.         while ((c=getc(fp)) != ' ') buffer[i++] = c;
  257.         buffer[i] = '\0';
  258. #if    0
  259.         printf("buffer=%s\n", buffer);
  260. #endif    /*0*/
  261.         sscanf(buffer, "%d,%1023s", &id, temp);
  262.         temp[1023] = '\0';
  263. #if    0
  264.         printf("read attr=%s,%d @ %d\n", temp, id, index);
  265. #endif    /*0*/
  266.         if (id <= 0) continue;
  267.         e = (attr_element_t *)my_malloc(sizeof(attr_element_t));
  268.         e->attributeid = id;
  269.         if (id > attr_maxid) attr_maxid = id;
  270.         e->attribute = (char *)my_malloc(strlen(temp) + 2);
  271.         strcpy(e->attribute, temp);
  272.         e->next = attr_hash_table[index];
  273.         attr_hash_table[index] = e;
  274.         ret ++;
  275.         if (index >= ATTR_HASH_TABLE_SIZE - 1) break;
  276.     }
  277.     fclose(fp);
  278.  
  279.     attr_name_table = (char **)my_malloc(sizeof(char *) * (ret=(ret >= (attr_maxid + 1) ? ret : (attr_maxid + 1))));
  280.     memset(attr_name_table, '\0', sizeof(char *) * ret);
  281.     for (i=0; i<ATTR_HASH_TABLE_SIZE; i++) {
  282.         e = attr_hash_table[i];
  283.         while (e!=NULL) {
  284.             attr_name_table[e->attributeid] = e->attribute;
  285.             e = e->next;
  286.         }
  287.     }
  288.     return ret;
  289. }
  290.  
  291. /***************************************************************************/
  292.  
  293. region_t *current_regions, *nextpos;    /* nextpos is hint into list */
  294.  
  295. /*
  296.  * Called during indexing before region_create.
  297.  * returns 0.
  298.  */
  299. int
  300. region_initialize()
  301. {
  302.     attr_num = 0;
  303.     attr_name_table = NULL;
  304.     memset(attr_hash_table, '\0', sizeof(attr_element_t *) * ATTR_HASH_TABLE_SIZE);
  305.     current_regions = nextpos = NULL;
  306.     return 0;
  307. }
  308.  
  309. /*
  310.  * creates a data structure containing the list of attributes
  311.  * which occur at increasing offsets in the given file -- future
  312.  * region_identify() calls use the "current" data structure.
  313.  * returns 0 if success, -1 if it cannot open the file.
  314.  */
  315. int
  316. region_create(name)
  317.     char    *name;
  318. {
  319.     FILE    *fp;
  320.     AVList    *al;
  321.     region_t *prl, *rl, *lastrl;
  322.     Template *t;
  323.     char    temp[1024];
  324.  
  325.     current_regions = nextpos = NULL;
  326.     if ((fp = fopen(name, "r")) == NULL) return -1;
  327.     init_parse_template_file(fp);
  328.  
  329.     lastrl = NULL;
  330.     while ((t = parse_template()) != NULL) {
  331.         /* do insertion sort of list returned by parse_template using offsets */
  332.         if ((t->url != NULL) && (strlen(t->url) > 0)) {
  333.             rl = (region_t *)my_malloc(sizeof(region_t));
  334.             /* Darren Hardy's Voodo :-) */
  335.                         /* The SOIF looks like this:  @TTYPE { URL\n */
  336.                         /* t->offset points to the @ */
  337.                         /* rl->offset points to the space before URL */
  338.                         /* rl->length includes the entire URL */
  339.                         rl->offset = t->offset + strlen(t->template_type) + 3;
  340.                         rl->length = strlen(t->url) + 1;
  341.             rl->attributeid = attr_insert_name("url", 3);
  342.  
  343.             if ((lastrl != NULL) && (lastrl->offset <= rl->offset)) {    /* go forward */
  344.                 prl = lastrl;
  345.                 while (prl->next != NULL) {
  346.                     if (prl->next->offset > rl->offset) {
  347.                         rl->prev = prl;
  348.                         rl->next = prl->next;
  349.                         prl->next->prev = rl;
  350.                         prl->next = rl;
  351.                         lastrl = rl;
  352.                         break;
  353.                     }
  354.                     else prl = prl->next;
  355.                 }
  356.                 if (prl->next == NULL) {
  357.                     rl->next = NULL;
  358.                     rl->prev = prl;
  359.                     prl->next = rl;
  360.                     lastrl = rl;
  361.                 }
  362.             }
  363.             else {    /* must go backwards and find the right place to insert */
  364.                 prl = lastrl;
  365.                 while (prl != NULL) {
  366.                     if (prl->offset < rl->offset) {
  367.                         rl->prev = prl;
  368.                         rl->next = prl->next;
  369.                         if (prl->next != NULL)
  370.                             prl->next->prev = rl;
  371.                         prl->next = rl;
  372.                         lastrl = rl;
  373.                         break;
  374.                     }
  375.                     else prl = prl->prev;
  376.                 }
  377.                 if (prl == NULL) {
  378.                     rl->next = current_regions;
  379.                     if (current_regions != NULL) current_regions->prev = rl;
  380.                     rl->prev = NULL;
  381.                     current_regions = rl;
  382.                     lastrl = rl;
  383.                 }
  384.             }
  385.  
  386. #if    0
  387.             printf("region url=[%d,%d]\n", rl->offset, rl->offset+rl->length);
  388. #endif    /*0*/
  389.         }
  390.  
  391.         al = t->list;
  392.         while(al != NULL) {
  393.             rl = (region_t *)my_malloc(sizeof(region_t));
  394.             rl->offset = al->data->offset;
  395.             rl->length = al->data->vsize;
  396.             attr_extract(temp, al->data->attribute);
  397.             rl->attributeid = attr_insert_name(temp, strlen(temp));
  398.  
  399.             if ((lastrl != NULL) && (lastrl->offset <= rl->offset)) {    /* go forward */
  400.                 prl = lastrl;
  401.                 while (prl->next != NULL) {
  402.                     if (prl->next->offset > rl->offset) {
  403.                         rl->prev = prl;
  404.                         rl->next = prl->next;
  405.                         prl->next->prev = rl;
  406.                         prl->next = rl;
  407.                         lastrl = rl;
  408.                         break;
  409.                     }
  410.                     else prl = prl->next;
  411.                 }
  412.                 if (prl->next == NULL) {
  413.                     rl->next = NULL;
  414.                     rl->prev = prl;
  415.                     prl->next = rl;
  416.                     lastrl = rl;
  417.                 }
  418.             }
  419.             else {    /* must go backwards and find the right place to insert */
  420.                 prl = lastrl;
  421.                 while (prl != NULL) {
  422.                     if (prl->offset < rl->offset) {
  423.                         rl->prev = prl;
  424.                         rl->next = prl->next;
  425.                         if (prl->next != NULL)
  426.                             prl->next->prev = rl;
  427.                         prl->next = rl;
  428.                         lastrl = rl;
  429.                         break;
  430.                     }
  431.                     else prl = prl->prev;
  432.                 }
  433.                 if (prl == NULL) {
  434.                     rl->next = current_regions;
  435.                     if (current_regions != NULL) current_regions->prev = rl;
  436.                     rl->prev = NULL;
  437.                     current_regions = rl;
  438.                     lastrl = rl;
  439.                 }
  440.             }
  441.  
  442. #if    0
  443.             printf("region %s=[%d,%d]\n", al->data->attribute, rl->offset, rl->offset+rl->length);
  444. #endif    /*0*/
  445.             al = al->next;
  446.         }
  447.         free_template(t);
  448.     }
  449.     finish_parse_template();
  450.     nextpos = current_regions;
  451.     fclose(fp);
  452.     return 0;
  453. }
  454.  
  455. /*
  456.  * frees the data structure created for the current file above.
  457.  * returns 0.
  458.  */
  459. int
  460. region_destroy()
  461. {
  462.     region_t *rl = current_regions, *trl;
  463.  
  464.     while (rl != NULL) {
  465.         trl = rl;
  466.         rl = rl->next;
  467.         free(trl, sizeof(region_t));
  468.     }
  469.     current_regions = nextpos = NULL;
  470.     return 0;
  471. }
  472.  
  473. /*
  474.  * returns attribute number [1..num_attr] which covers (inclusive)
  475.  * the region * [offset, offset+len] in the "current" file, 0 if none.
  476.  * called during indexing after region_create, and search after
  477.  * attr_load_names. Do not need sophisticated interval trees here!
  478.  */
  479. int
  480. region_identify(offset, len)
  481.     int    offset, len;
  482. {
  483.     region_t *rl;
  484.  
  485.     if (nextpos == NULL) nextpos = current_regions;
  486.     rl = nextpos;
  487.     while (rl!=NULL) {
  488.         if (rl->offset > offset + len)
  489.             goto backwards;            /* definitely before: can be earlier region OR hole */
  490.         else if ((rl->offset <= offset) && (rl->offset + rl->length >= offset + len))
  491.             return rl->attributeid;        /* definitely within */
  492.         else if (rl->offset + rl->length < offset)
  493.             nextpos = rl = rl->next;    /* definitely after: later region */
  494.         else return 0;                /* overlapping: error */
  495.     }
  496.     return 0;                    /* reached end of file */
  497.  
  498. backwards:
  499.     while (rl!=NULL) {
  500.         if (rl->offset > offset + len)
  501.             nextpos = rl = rl->prev;    /* definitely before: earlier region */
  502.         else if ((rl->offset <= offset) && (rl->length + rl->length >= offset + len))
  503.             return rl->attributeid;        /* definitely within */
  504.         else if (rl->offset + rl->length < offset)
  505.             return 0;            /* hole */
  506.         else return 0;                /* overlapping: error */
  507.     }
  508.     return 0;                    /* reached end of file */
  509. }
  510.  
  511. #else    /*STRUCTURED_QUERIES*/
  512.  
  513. int attr_num = 0;
  514.  
  515. char *attr_id_to_name(id)
  516.     int    id;
  517. {
  518.     return NULL;
  519. }
  520.  
  521. int attr_name_to_id(name)
  522.     char    *name;
  523. {
  524.     return 0;
  525. }
  526.  
  527. int attr_dump_names(name)
  528.     char    *name;
  529. {
  530.     return 0;
  531. }
  532.  
  533. int attr_load_names(name)
  534.     char    *name;
  535. {
  536.     return 0;
  537. }
  538.  
  539. int attr_free_table()
  540. {
  541.     return 0;
  542. }
  543.  
  544. int region_initialize()
  545. {
  546.     return 0;
  547. }
  548.  
  549. int region_desrtroy()
  550. {
  551.     return 0;
  552. }
  553.  
  554. int region_create(name)
  555.     char    *name;
  556. {
  557.     return 0;
  558. }
  559.  
  560. int region_destroy()
  561. {
  562.     return 0;
  563. }
  564.  
  565. int region_identify(offset, len)
  566.     int    offset, len;
  567. {
  568.     return 0;
  569. }
  570. #endif    /*STRUCTURED_QUERIES*/
  571.